1. Technical Field
The present invention relates generally to static information storage and retrieval systems, and more particularly to associative memories, which are also referred to as content or tag memories.
2. Background Art
In a content addressable memory (CAM), an input word (the data-in word) consists of an ordered group of K bits which is compared bit-by-bit with a plurality of stored words in the CAM. If all of the bits of one of the stored words match those of the data-in word, the address of that stored word is output to the user. Sometimes more than one stored word matches the data-in word. In this case, usually only one address is output, based on a pre-specified priority criterion.
On the other hand, in many cases not all bits need to match when such comparisons are performed. Some bits in a stored word may then be masked out, and not compared with the corresponding bits in the data-in word. It is considered a legitimate match here if the stored word matches the data-in word for all but the masked bits. Technically, a masked bit always returns a match condition so that it does not affect the overall result.
A CAM wherein stored words must be compared bit-by-bit without exception is called a binary CAM, and its memory cells have two logic states: a xe2x80x9c0xe2x80x9d state and a xe2x80x9c1xe2x80x9d state. In contrast, a CAM that allows stored words to have masked bits is called a ternary CAM. The memory cell of a ternary CAM has three logic states: a xe2x80x9c0xe2x80x9d state, a xe2x80x9c1xe2x80x9d state, and a xe2x80x9cDON""T CARExe2x80x9d state that returns an unconditional match.
FIG. 1 shows a typical stored word in a binary CAM. It consists of a row of SRAM cells having differential outputs DSk and DSkB (DSk bar) which are compared with corresponding differential data-in lines Dlk and DlkB through a comparator. The set of connections for the comparator logic, also commonly termed a logic comparison function, is equivalent to (DSk*DlkB)+(DSkB*Dlk)=DSk(+)Dlk, which is effectively an EXCLUSIVE OR function. At the beginning of each compare cycle a match line (ML) is pulled high by connection to a voltage source VDD) via a pre-charge gate (MP0; typically a PMOS device), and all of the data lines Dlk and DlkB, where k=1 . . . K, are held low. The pre-charge gate is then turned off, leaving the match line floating. At the same time the Dlk data lines are driven by the input data. If DSk=Dlk then DSk (+)Dlk=0 and the cell k leaves the match line alone. This is a match condition.
On the other hand, if DSkxe2x89xa0Dlk then DSK(+)Dlk=1 and one of the series pairs of pass-gates (typically NMOS devices) will conduct and discharge the match line to ground. This is a non-match condition. Since it takes only one non-matched cell to discharge the match line to ground, a word is said to match with the data-in word if DSk=Dlk for all k=1 . . . K. That is if the match line stays high. Since all cells are counted in the compare here this is a binary CAM. The two states of the cell are: a xe2x80x9c1xe2x80x9d state with DSK=1 (high) and DSkB=0 (low); and a xe2x80x9c0xe2x80x9d state with DSK=0 and DSkB=1.
FIG. 2 shows a typical stored word in a ternary CAM. Since the memory cell of a ternary CAM needs three states, two SRAM cells sharing a comparator form a ternary cell. There are now three usable states: a xe2x80x9c1xe2x80x9d state, with DS1=1 and DS2=0; a xe2x80x9c0xe2x80x9d state with DS1=0 and DS2=1; and a xe2x80x9cDON""T CARExe2x80x9d state with DS1=DS2=0. The data-in lines Dl and DlB are connected in the same fashion as in FIG. 1, forming an EXCLUSIVE OR logic function. The pre-charged match line (ML) stays high if Dl1=1and the cell is in the xe2x80x9c1xe2x80x9d state or Dl1=0 and the cell is in the xe2x80x9c0xe2x80x9d state. When the cell is in the xe2x80x9cDON""T CARExe2x80x9d state, with both series pairs of pass-gates cut off and preventing the match line discharging to ground, a match condition is guaranteed and the cell has no effect on the overall result. Notice that the DSk and DSkB outputs of all odd numbered SRAM are the mirror images of the associated even numbered SRAM for easy layout.
As can be seen by comparing FIG. 1 and FIG. 2, the only difference between a binary CAM cell and a ternary CAM cell is that in a ternary cell a single comparator is shared by two SRAM cells. Most ternary CAM on the market today uses this configuration to save die area and to simplify component connection. Such CAM can still be used as a binary cell, but then the die area is not used efficiently, because two SRAM cells are being used to hold only one bit of data.
Another major concern regarding the efficient use of CAM is power consumption. As those skilled in the electronic arts well know, reducing power consumption is generally desirable in a circuit. However, in CAM it is an increasingly concern because CAM is often used in portable, battery operated devices and the consumption of power relates directly to how long such devices can be operated. Any reduction in CAM power consumption is therefore a highly desirable benefit.
FIG. 3 depicts a logical approach, based on industry trends, to achieving a binary-ternary CAM. It should be noted, however, that the present inventors do not know of any products actually using this approach. FIG. 3 is included here as a useful comparison to the present invention. Yet another manner of achieving binary-ternary CAM, and one which takes a much different approach, is described in U.S. Pat. No. 6,362,992.
As can also be seen by comparing FIGS. 1-3, a common feature of CAM (and many other parallel comparison circuits, for that matter) is the use of a match line (ML). Only a few memory cells are shown in the examples, with all in a single row connected to only a single match line. In actual practice, there typically will be thousands of cells in each row and hundreds or thousands of such rows, each having a respective match line. Each such match line is pre-charged with a voltage and when a match condition occurs the match line discharges, nominally to ground. Conceptually similar circuits can be constructed, but are not common, where the match line is pre-grounded and a match condition causes charging to some voltage level which is detected. Unfortunately, these approaches to match detection have a number of problems.
One can consider just one row. In view of the large number of cells present, it should be clear that the match line for such a row will have an appreciable capacitance. The pre-charge sub-circuit (e.g., MP0 in FIG. 1) has to handle this, and will typically take up a relatively large amount of die space or xe2x80x9creal estate.xe2x80x9d The row also necessarily operates at a particular clock rate, performing pre-charging, comparison, and match detection in each cycle. In this approach, the match line necessarily also runs at that clock frequency. However, as those skilled in the electronic arts also accept as a maxim, it is generally desirable to reduce sub-circuit frequency wherever possible, while maintaining overall system frequency. Lower operating frequency typically correlates with reduced power consumption, component life, etc. Additionally, switching high power and reactive loads at high frequency is undesirable because of possible collateral effects due to electro-magnetic radiation.
In summary, it is desirable to have a more flexible CAM, which can be efficiently applied as either binary or ternary CAM. It is also desirable to have CAM, in the form of binary CAM, ternary CAM, or configurable binary-ternary CAM, which consumes less power. And it is further desirable to have CAM which operates sub-circuits at low effective frequency, particularly including the match line sub-circuit.
Accordingly, it is an object of the present invention to provide a CAM which is configurable to operate in either binary mode or ternary mode, yet which is efficiently able to utilize all memory cells in either mode.
Another object of the invention is to provide a CAM which provides substantial power savings.
Briefly, one preferred embodiment of the present invention is a content addressable memory (CAM). The CAM includes an input sub-circuit to present input data to multiple cell sub-circuits. A further included match sub-circuit has a match-high line, a match-low line, and a pre-charge sub-circuit. The pre-charge sub-circuit is able to connect the match-high line to a voltage source, to charge it, and also to connect the match-low line to a ground, to discharge it. The cell sub-circuits each compare one bit of the input data with one bit of pre-stored storage data and determine whether pre-specified match criteria are met. If so, the cell sub-circuit connects the match-high line and match-low line, thereby signaling detection of a mismatch condition.
Briefly, another preferred embodiment of the present invention is a content addressable memory (CAM) for binary mode comparison of input bits with storage bits. The CAM includes an input sub-circuit to present the input bits to multiple cell sub-circuits. A further included match sub-circuit has a match-high line, a match-low line, a pre-charge sub-circuit, and multiple match-gates, at least equaling the cell sub-circuits in number. The pre-charge sub-circuit is able to controllably bring the match-high line to a high state and the match-low line to a low state. Each match-gate is able to operationally connect the match-high line with the match-low line in response to a match signal. The cell sub-circuits each store one of the storage bits and generate a respective match signal based on the states of the input bit and its storage bit, thereby permitting the CAM to compare the input bits with the storage bits to detect a mismatch condition.
Briefly, another preferred embodiment of the present invention is a content addressable memory (CAM) for ternary mode comparison of input bits with storage bits. The CAM includes an input sub-circuit to present the input bits to multiple composite cells. A further included match sub-circuit has a match circuit including a match-high line, a match-low line, a pre-charge sub-circuit, and multiple match-gates, at least equaling the cell sub-circuits in number. The pre-charge sub-circuit is able to controllably bring the match-high line to a high state and the match-low line to a low state. Each match-gate is able to operationally connect the match-high line with the match-low line in response to a match signal. The composite cells each store one of the storage bits and one of the mask bits as a ternary unit having three possible states: 1, 0, and X, wherein X represents masked. The composite cells then each generate a respective match signal based on the states of the input bit and the ternary unit, thereby permitting the CAM to compare one of the input bits with one of the storage bits and one of the mask bits to detect a mismatch condition.
And, briefly, another preferred embodiment of the present invention is a content addressable memory (CAM) for comparison of a data set in either binary mode or ternary mode. The CAM includes an input circuit suitable for presenting input bits from the data set to multiple composite cells. A further included match circuit has a match-high line, a match-low line, a pre-charge sub-circuit, and multiple match-gates, at least equaling the composite cells in number. The pre-charge sub-circuit is able to controllably bring the match-high line to a high state and the match-low line to a low state. Each match-gate is able to operationally connect the match-high line with the match-low line in response to a match signal. The composite cells selectively operate in either the binary mode or the ternary mode. In the binary mode, each composite cell stores two storage bits, receives two input bits from the input circuit, and generates two match signals respectively based on the states of an input bit and a storage bit, thereby permitting the CAM to compare the data set with the storage bits in binary manner to detect a mismatch condition. In the ternary mode, each composite cell stores one storage bit and one mask bit as a ternary unit having three possible states: 1, 0, and X, wherein X represents masked. The composite cells each receive one input bit from the input circuit and generate a respective match signal based on the states of the input bit and the ternary unit, thereby also permitting the CAM to compare the data set with the storage bits and the mask bits in ternary manner to detect a mismatch condition.
An advantage of the present invention is that it provides a CAM that is configurable to operate in either binary mode or ternary mode while efficiently utilizing all memory cells.
Another advantage of the invention is that it provides substantial power savings in input data handling, by floating signals that do not need to be changed, and thereby not requiring reconditioning (charging or discharging) of those signals for later use.
And another advantage of the invention is that it halves the operation rate or frequency of key sub-circuits which handle and consume substantial power. This directly avoids direct adverse frequency related effects in the CAM, such as electromagnetic interference. Concurrently, this provides substantial further power savings in match detection, by reduced operation of large devices and capacitances, while still providing match detection capability during every clock cycle.